/*
Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
*/

class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> res;
        int leftpos = findPos(0, n-1, A, target, true);
        res.push_back(leftpos); 
        /*int rightpos = findPos(0, n-1, A, target, false);
        res.push_back(rightpos);*/
        if (leftpos == -1) res.push_back(-1);
        else {
            // find right index
            while (leftpos < n && A[leftpos] == target) leftpos++;
            res.push_back(leftpos-1);
        }
        return res;
    }
private:
    int findPos(int low, int high, int A[], int target, bool left) {
        if (low > high) return -1;
        int pos, mid = (low + high) /2;
        if (A[mid] < target) pos = findPos(mid+1, high, A, target, left);
        else if (A[mid] > target) pos = findPos(low, mid-1, A, target, left);
        else {
            if (left) pos = findPos(low, mid-1, A, target, left);
            else pos = findPos(mid+1, high, A, target, left);
            if (pos==-1) pos=mid;
        }
        return pos;
    }
};

#if 0
class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> res = {-1, -1};
        if (!n) return res;
        // find target and left index
        int found = 0, low = 0, high = n-1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (A[mid] >= target) {
                if (A[mid] == target) {
                    found = 1;
                }
                high = mid-1;
            } else {
                low = mid+1;
            }
        }
        if (!found) return res;
        res.clear(); high++;
        res.push_back(high);
        // find right index
        while (high < n && A[high] == target) high++;
        res.push_back(high-1);
        return res;
    }
};
#endif
